package org.basis.algorithm.tree;

import org.basis.algorithm.tree.common.Node;

import java.util.Stack;

/**
 * 检查是否是二叉搜索树
 *
 * @author Mr_wenpan@163.com 2021/12/22 11:09
 */
public class CheckBinarySearchTree {

    public static void main(String[] args) {

    }

    /**
     * 二叉搜索树，对于每个子树他的头节点一定大于他的左孩子，小于他的右孩子
     */
    public static boolean isBst(Node head) {
        if (head == null) {
            return true;
        }
        // 问左右孩子要结果
        boolean leftRes = isBst(head.left);
        boolean rightRes = isBst(head.right);

        boolean isBst = true;
        if (head.left != null && head.data <= head.left.data) {
            isBst = false;
        }
        if (head.right != null && head.data >= head.right.data) {
            isBst = false;
        }

        // 向上返回自己的结果
        return leftRes && rightRes && isBst;
    }

    public static boolean isBst2(Node head) {
        if (head == null) {
            return true;
        }
        // 遍历整棵树，依次检查每个节点(这里采用非递归先序遍历)
        Stack<Node> stack = new Stack<>();
        stack.push(head);

        while (!stack.isEmpty()) {
            // 弹出就检查
            Node pop = stack.pop();
            if (pop.left != null && pop.data <= pop.left.data) {
                return false;
            }
            if (pop.right != null && pop.data >= pop.right.data) {
                return false;
            }
            if (pop.right != null) {
                stack.push(pop.right);
            }
            if (pop.left != null) {
                stack.push(pop.left);
            }
        }

        return true;
    }


}
